Theo chỉ thị của lãnh tụ Việt Minh Hồ Chí Minh, cuối năm 1944, một số đội viên xuất sắc của các đội Cứu quốc quân và du kích Việt Minh được tập hợp để thành lập 1 đội vũ trang làm nhiệm vụ tuyên truyền lấy tên là Việt Nam Tuyên truyền Giải phóng quân. Nhận thấy việc nên có 1 nhạc hiệu cho đội, ông Võ Nguyên Giáp đã giao cho Hoàng Văn Thái, 1 đội viên của đội, về việc sáng tác 1 bài hát làm nhạc hiệu. Là 1 người có chút ít kiến thức về nhạc lý, ngay trong đêm 21/12/1944, trước ngày thành lập Đội, ông Hoàng Văn Thái đã sáng tác 1 bản hành khúc lấy tên là "Phất cờ nam tiến"[2]. Ngay chiều ngày hôm sau, bài hát lần đầu tiên được trình diễn trong buổi lễ tuyên thệ của Việt Nam Tuyên truyền Giải phóng quân.